#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INT_SIZE 100
#define LIST_INCREATMENT 10
#define MAX_SIZE 100
typedef int Status;
typedef int ElemType;

typedef struct component
{
    ElemType data;
    int cur;
} component, SLinklist[MAX_SIZE];

Status init_space(SLinklist *head) // head是一个指针指向结构体数组的首地址,也就是space[0]的地址
{

    for (int i = 0; i < MAX_SIZE; ++i)
    {
        (*head)[i].data = 0;    // 初始化所有节点的值
        (*head)[i].cur = i + 1; // 链接所有节点
    }
    (*head)[MAX_SIZE - 1].cur = 0; // 最后一个地址设置指向为0,表示到头了;
    return OK;
}

void show_list(SLinklist *head) // 只能输出初始space,没什么用,但是看懂不容易
{
    /*
    在 show_list 函数中，component *p = head[0]; 会将 head[0] 这个数组元素解析为 component 结构体指针，
    但实际上 head[0] 是一个 component 结构体，而不是指针。因此，应该改成 component *p = &(*head)[0];
    将 head[0] 取地址后赋给 p，这样才能正确地访问静态链表。
    */
    component *p = &(*head)[0]; // head[i]都是结构体
    while (p->cur != 0)
    {
        p = &(*head)[p->cur];
        printf("%d ", p->data);
    }
    printf("%d ", p->data);
    printf("\n");
}

// 更加简洁的写法
void new_show_list(SLinklist *head)
{
    for (int i = (*head)[0].cur; i != 0; i = (*head)[i].cur)
    {
        printf("%d ", (*head)[i].data);
    }
    printf("\n");
}

void pointer_to_show_components(SLinklist *head, component *l) // 给定结构体指针,输出到底(cur==0)
{
    while (l->cur != 0)
    {
        l = &(*head)[l->cur];
        printf("%d ", l->data);
    }
    printf("\n");
}

// 分配空间函数
int malloc_sl(SLinklist *head) // head是结构体指针,指向的是结构体
{
    // 思路：检查第一个节点是否存在,存在就返回这个节点的位置并删除该节点,不存在返回0.
    int i = (*head)[0].cur; // 返回目标的所在位置
    if (i != 0)             // 不是0就是存在
    {
        (*head)[0].cur = (*head)[i].cur; // 修改space
        return i;                        // 返回
    }
    else
    {
        return 0;
    }
}

Status head_insert(SLinklist *head, component *l, ElemType e, int i) // 头插法
{
    // 使用第i个结构体,存放e的值,使用头插法插入到la中
    (*head)[i].data = e;     // 放值
    (*head)[i].cur = l->cur; // 把后面连接起来
    l->cur = i;              // 把头链接起来
    return OK;
}

Status init_component(component *c) // 初始化节点
{
    c->cur = 0;
    c->data = 0;
    return OK;
}

Status free_sl(SLinklist *head, int k) // 释放第k个节点
{
    // 思路:把k节点链接到space表就可以
    (*head)[k].cur = (*head)[0].cur; // 链接后面
    (*head)[0].cur = k;              // 链接前面
    return OK;
}

int locateElem(SLinklist *head, component *la, ElemType e) // 在链表中查找e的值,返回位置
{
    // 在静态链表中查询第一个与e相等的数值,返回位置否则0
    int j = 1;
    la = &(*head)[la->cur]; // 从第一个节点开始
    while (la->data != e && la->cur != 0)
    {
        la = &(*head)[la->cur]; // 往后移la指针
        j++;
    }
    if (la->data == e)
    {
        return j;
    }
    else
    {
        return 0;
    }
}

void difference(SLinklist *head, component *la, int a[], int b[]) // 实现(A-B)交(B-A)
{
    // a和b分别是集合a和b的指针
    // 先把集合a存储到la链里,然后不断加入b中的值
    // 每次加入前扫描链表,存在该元素就删除,不存在就插入到尾部
    for (int i = 0; i < 10; i++)
    {
        head_insert(head, la, a[i], malloc_sl(head)); // 头插法插入数组a的数据
    }
    pointer_to_show_components(head, la); // show()一下

    for (int i = 0; i < 10; i++) // 对b的元素挨个循环
    {
        printf("%d ", b[i]); // 现在输出b的值,为了最后验证对错
        component *p = la;
        int is_break = 0;
        int the_data = b[i]; // 取一下值
        // 如何判断到了表最后?
        component *last_p = NULL;
        while (p->cur != 0) // 这个循环需要完成查询是不是有相同元素的功能,有就立刻删除进行下一个数的循环,否则插入
        {
            component *last_temp_p = p; // 记录p的上一个位置
            p = &(*head)[p->cur];       // p指向下一个节点
            if (p->data == the_data)    // 如果A里存在这个值(删除这个数,继续下一个数循环)
            {
                last_p = last_temp_p; // 局部变量传递给函数内变量,其作用是记录相同节点前一个节点(便于删除用)
                is_break = 1;         // 设置一个观察点看看是不是有相等的值
                break;
            }
        }
        // 要么到头了要么存在相同的数
        if (p->cur == 0 && is_break == 0) // 到头了且是正常结束的。代表没有这个元素在链表a里面
        {
            // 插入the_data;
            int nom = malloc_sl(head);     // 分配空间
            init_component(&(*head)[nom]); // 初始化分配到空间
            (*head)[nom].data = the_data;  // 存储值
            p->cur = nom;                  // 尾插(进行链接)
        }
        else if (p->cur != 0) // 没到头(在中间发现了重复的值)
        {
            int i = last_p->cur;  // 记录要删除节点的位置
            last_p->cur = p->cur; // 删除这个节点
            free_sl(head, i);     // 释放空间
        }
        else if (p->cur == 0 && is_break == 1) // 最后位置重复了
        {
            free_sl(head, last_p->cur);
            last_p->cur = 0;
        }
    }
    printf("\n");
}

int main()
{
    // 建立一个space,space为全体数据空间;
    SLinklist space;
    // 初始化space
    init_space(&space); // 传入space的首地址
    // 设置输出space
    // show_list(&space);     //  输出数据空间(sqace)的一种写法
    // new_show_list(&space); // 一种比较好的输出数据空间(sqace)的写法
    // 如果有一个结构体指针指向space的头节点,那么就可以输出这条space(剩余空间)链
    component *s = &space[0]; // 指向space的第一个结构体
    pointer_to_show_components(&space, s);
    // 创建链a的头节点指针,并且分配空间[ps:la为指针,指向一个结构体,而*la就是指向的结构体]
    component *la = (component *)malloc(sizeof(component)); // 新建结构体指针,指向链a的第一个节点
    init_component(la);                                     // 对节点初始化
    // 对a链表赋值
    for (int i = 1; i < 5; ++i)
    {
        // 头插法，插入1,2,3,4
        ElemType e = i;
        head_insert(&space, la, e, malloc_sl(&space)); // 使用malloc_sl分配的空间把e的值头插到la中
    }
    // 输出链表a
    pointer_to_show_components(&space, la); // la为结构体指针,也是链表a的头指针
    // free_sl(space,2);                      // 释放第k个节点
    // 查找链表里的一个数
    int loc = locateElem(&space, la, 2); // 在a链表查找2的位置
    printf("\n2的位置是:%d\n", loc);

    // 实现课本算法(A-B)交(B-A)
    int a[10], b[10];
    for (int i = 0; i < 10; i++)
    {
        a[i] = i * 2 - 1;
        b[i] = i + 1;
    }

    // 释放la的存储空间(清空a链表)
    while ((*la).cur != 0) // 可以使用结构体写法也可以使用指针写法
    {
        int i = (*la).cur;
        (*la).cur = space[i].cur; // 相当于在a链表中移除a的第一个节点.space[i]是移除的节点。这一句意思是la头节点指向第一个节点的下一个节点
        free_sl(&space, i);       // 释放i节点空间(重新把i插入space里)
    }
    printf("输出空的a链表:\n");
    pointer_to_show_components(&space, la); // 输出la发现无输出代表la已经的内容已经释放
    printf("已输出完成\n");
    // 上述代码为清空a链表
    difference(&space, la, a, b);           // 算法2.17
    pointer_to_show_components(&space, la); // 输出算法运行后的结果
}
/*
1.数组传递的时候不是不需要写取地址符吗？
    在函数调用中，对于数组的名称，它本身已经表示了一个指向数组首元素的指针，
因此在函数调用时无需再添加取地址符&，即数组名就是指向数组首元素的指针。
但是，当我们需要传递一个指向整个数组的指针时，就需要使用取地址符&来获取数组的首地址。
在这个例子中，SLinklist是一个结构体类型的数组，当我们需要传递整个SLinklist数组时，
就需要使用取地址符&来获取数组的首地址，以便在函数内部可以正确地操作整个数组。


2.那意思是如果我的主函数里init_space()括号里写space,相当于只是传递了space[0]这一个结构体过去，其他的结构体并没有传递过去对吗?
    是的，如果在主函数中调用init_space(space)，实际上传递给函数的是space[0]这个结构体的地址，
而不是整个space数组的首地址。这样在函数内部就只能操作到space[0]这个结构体，而无法正确地操作整个数组。
因此，在这个例子中，为了正确地传递整个数组，需要在调用函数时使用取地址符&来获取数组的首地址，
即使用init_space(&space)。这样函数内部就可以正确地操作整个space数组。

*/